package com.zklh.leetcode.top100;

import java.util.Arrays;

/**
 * 打家劫舍算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/10
 */
public class Solution198 {

    private int[] cache;

    public int rob(int[] nums) {
        cache = new int[nums.length];
        Arrays.fill(cache, -1);
        return rob(nums, 0);
    }

    private int rob(int[] nums, int start) {
        if (start > nums.length - 1) {
            return 0;
        }

        if (nums.length - 1 - start <= 1) {
            return Math.max(nums[start], nums[nums.length-1]);
        }

        if (cache[start] != -1) {
            return cache[start];
        }

        cache[start] = Math.max(nums[start] + rob(nums, start+2), nums[start+1] + rob(nums, start+3));
        return cache[start];
    }

    public static void main(String[] args) {
        Solution198 solution198 = new Solution198();
        System.out.println(solution198.rob(new int[]{1, 2, 3, 1}));
        System.out.println(solution198.rob(new int[]{2, 7, 9, 3, 1}));
    }
}